package sort;

import java.util.Arrays;
import java.util.Objects;

/**
 * 插入排序
 *
 * @auther yang
 * @date 2022/3/16 15:35
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {3, 5, 0, 8, 99, 1, 0};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] a) {
        if (Objects.isNull(a) || a.length < 2)
            return;
        sort(a, 0);
    }

    // 插入排序的递归算法
    private static void sort(int[] a, int index) {
        if (index >= a.length) return;
        int i = index - 1;
        int temp = a[index];

        // index 前边的数比 a[index] 大, 就整体后移
        while (i >= 0 && a[i] > temp) {
            a[i + 1] = a[i];
            --i;
        }

        // 把 temp 放到指定位置
        a[i + 1] = temp;

        sort(a, index + 1);
    }

}
